//
// Created by bleedingfight on 2020/6/25.
//
#include "findTargetSumWays.h"
int findTargetSumWays(std::vector<int>& nums, int S){
    std::vector<int> dp = std::vector<int>(2001,0);
    dp[nums[0]+1000] = 1;
    dp[-nums[0]+1000] += 1;
    for(int i=1;i<nums.size();i++){
        std::vector<int>next = std::vector<int>(2001,0);
        for(int sum=-1000;sum<=1000;sum++){
            if(dp[sum+1000]>0){
                next[sum+nums[i]+1000]+=dp[sum+1000];
                next[sum-nums[i]+1000]+=dp[sum+1000];
            }
        }
        dp = next;
    }
    return S>1000?0:dp[S+1000];
}

